The term “Chien search” is used herein to refer to any typically iterative method or apparatus for determining roots of polynomials defined over a finite field. The term is also used herein to refer to any method or apparatus used for finding the roots of error-locator polynomials encountered in decoding, e.g., Reed-Solomon codes and BCH codes in various applications including but not limited to flash memory and other data storage applications, and data communications applications.
The error locator polynomial (denoted Λ) has the following format:Λ(x)=Λ0+Λ1*x+Λ2*x2+ . . . +Λt*xt  (Equation 1)
The Chien search includes evaluating the error locator polynomial for multiple elements of a Galois field GF(2m) over which the error locator polynomial is defined. The elements are powers of the primitive element in the field, alpha (α).
Accordingly, the Chien search includes evaluating the error locator polynomial for various powers of alpha, by setting powers of alphas in equation 1 the following sets of equations are obtained:Λ(α)=Λ0+Λ1*α+Λ2*α2+ . . . +Λt*αt Λ(α2)=Λ0+Λ1*α2+Λ2*α4+ . . . +Λt*α2t Λ(αm)=Λ0+Λ1*αm+Λ2*α2m+ . . . +Λt*αmt 
The different powers of α are all elements in a finite field (such as a Galois field) over which the error locator polynomial is defined. Any power of alpha for which the above error locator polynomial is zero, is termed a root. These roots provide an indication about the location of the error in the received or read data. In other words, if αn is a root of the error locator polynomial then if binary BCH code is being used, an error has occurred in bit n of the data being read or received. In BCH, each error is a flipped bit. In Reed-Solomon, each error is a symbol in which at least one bit is wrong.
The evaluation of the error locator polynomial can be implemented in an iterative manner by a hardware circuit 10 that is illustrated in FIG. 1. Hardware circuit 10 includes: (i) a group of registers 12(1)-12(t) that are initially fed with the coefficients (Λ1, Λ2 . . . Λt) of the error locator polynomial, (ii) a group of Galois multipliers 14(1)-14(t) that multiply a previous content of registers 12(1)-12(t) by various powers of alpha (α, α2, . . . αt) to provide preliminary results that are written to the registers and are also provided to an adder, (iii) a Galois adder 16 that adds the preliminary results to provide a Chien search result. During each iteration a previous content of the k'th register is multiplied by αk. A content of the k'th register is denoted λk, the m'th bit of that register is denoted λk,m. If the Chien search result equals to minus one (or plus one for a binary field) then a root is found. (It is noted that if the Chien search result equals to zero than a root is found, when considering Λ0 which always equals to 1.
The evaluation of the error locator polynomial can also be evaluated in parallel by a hardware circuit 20 that is illustrated in FIG. 2A. Hardware circuit 20 includes: (i) a group of registers 12(1)-12(t) that are initially fed with the coefficients (Λ1, Λ2 . . . ,Λt), (ii) multiple groups of Galois multipliers 14(1,1) . . . 14(1,t) . . . 14(p,1) . . . 14(p,t) that multiply a previous content of registers 12(1)-12(t) by various powers of alpha (α, α2, . . . αt)to provide preliminary results that are provided to Galois adders, wherein Galois multipliers of different groups of Galois multipliers can receive different powers of alpha; wherein the preliminary results of one group of Galois multipliers are written to registers 12(1)-12(t), (iii) a group of Galois adders 16(1)-16(p)—each group of Galois multipliers is connected to a dedicated Galois adder that provides a Chien search result. Accordingly, hardware circuit 20 provides p Chien search results per iteration. The parallel hardware that is described in FIG. 2A can be also implemented in a variant way, as described in FIG. 2B. In this parallel architecture all the multipliers 14(1,1) . . . 14(p,1) are all connected to the same register 12(1). In the same way all the multipliers 14(1,t) . . . 14(p,t) are all connected to the same register 12(t).
It is noted that elements of a Galois field GF(pn) can be represented as polynomials of degree strictly less than n over GF(p). Operations are then performed modulo R where R is an irreducible polynomial of degree n over GF(p), for instance using polynomial long division.
The constant multipliers 14(1,1) . . . 14(p,1) includes a modulo R operation (R is an irreducible polynomial of degree n over GF(p)).
Referring back to the examples set forth in FIG. 1, FIG. 2A and FIG. 2B, the Galois multipliers and Galois adders include many logic gates. The number of gates in Galois multipliers and Galois adders can be responsive to the number of bits n in the variables that are being added to each other or multiplied with each other. The number of gates in Galois multipliers, and specifically in constant multipliers (multipliers that one of the multiplicand is a constant) can be responsive to the irreducible polynomial. In addition, the number of gates in Galois constant multipliers can be responsive to the number of set bits (‘1’) in the powers of a as well as their location.
For example, an adder that adds two n-bit numbers in the Galois field is about 2-bit XOR gates. Even more gates are required to implement Galois adder 16 that adds J n-bit numbers. Another example is that constant multiplier which its constant multiplicand is 101010101010101 (15 bits) consume much more gates than a constant multiplier which its constant multiplicand is 000000000001111 (15 bits). The second constant multiplicand has less set bits (1), and the sets bits are located in the LSB (Least Significant Bit).
Yet for another example, FIG. 3 illustrates an area consumed by sixty six groups of four Galois constant multipliers each, wherein each Galois constant multiplier performs a multiplication between two n-bits number in the Galois field. Graph 20 illustrates the number of set bits in coefficients (α, α2, . . . , αt), the x-axis represents the power of alphas, and graph 30 illustrates the area consumed by the Galois multipliers. It is apparent that there is a correlation between the number of set bits in the coefficients (α, α2, . . . , αt) and the area consumed by the respective Galois multiplier.
There is a growing need to provide a compact Chien search based decoding apparatus and method.